With the rapid growth of the Internet overlay networks have been increasingly used to deploy network services. Examples of such services include application-layer multicast (ALM) services, peer-to-peer to file sharing and overlay path routing services. However, to provide such services to a high standard it is important to know the topology of the underlying network. For example, in the case of ALM services it has been shown that topology-aware ALM can achieve substantially lower end-to-end delay, low physical link stress and high-tree bandwidth.
Various methods have been proposed to infer the topology of an underlying network. In particular, traceroute-like tools are often used to extract router-level path information between a pair of hosts. Traceroute is a widely used and well-defined measurement tool in the Internet. The specification of traceroute is defined in G. Malkin, “Traceroute Using an IP Option”, IETF RFC 1393 (January 1993), available at filing from http://www.ietforg/rfc/rfc1393.txt?number=1393. Traceroute is implemented using ICMP (Internet Control Message Protocol) messages that are sent from a source to a destination. The source transmits to a destination an IP datagram with a certain TTL (time-to-live) value and each router that handles the datagram is required to decrement the TTL value by one. When a router receives an IP datagram whose TTL is 1, the datagram is thrown away and the router returns an ICMP “time exceeded” error message back to the source. This error message includes the router name, router IP address and round-trip-time (RTT) to the source. The source therefore sends out to the destination a succession of IP datagrams with increasing TTL values and each datagram can identify one router in the path. In addition, if the datagram arrives at the destination with an unused port number (usually larger than 30,000) the destination's host UDP module generates an ICMP “port unreachable” error message that is returned to the source. Using these return messages the router-level path can be identified.
However, some routers process ICMP messages differently from each other. Some do not return ICMP error messages at all and consequently such routers appear as unknown and are conventionally indicated by the symbol “*” in the traceroute results. Other routers may return ICMP error messages only when their workload is light such that on some occasions the router appears in the traceroute results as a normal router, while on other occasions the router is unknown. Other routers may simply discard the ICMP messages and therefore all subsequent routers in the path appear as unknown. In this application routers that do not return ICMP messages at all are referred to as “type-1 routers”, routers that return ICMP messages only when their loading is light are referred to as “type-2 routers”, and routers that simply discard ICMP messages are referred to as “type-3 routers”.
Traceroute results therefore provide details of router with known IP addresses and these are conventionally called known routers. Unknown routers without an explicit IP address are referred to as anonymous routers.
FIG. 1 shows in Table I an example of typical traceroute results obtained from three experimental trials conducted from a server at The Hong Kong University of Science and Technology with www.sohu.com as the destination. The names, IP addresses and round-trip delays (including transmission delay, propagation delay, router processing delay and queuing delay) of the intermediate routers are all shown, but it will be seen that the third router is an anonymous router about which no information is known other than its presence in the path.
Topologies can be inferred from such traceroute results. To infer an underlying topology from traceroute results each occurrence of an anonymous router can be considered to be unique (ie each anonymous router corresponds to a different router) however this leads to high inflation of anonymous routers in the resulting inferred topology. This can be seen from the example of FIG. 2(a) that shows an example of an actual path topology. Here hosts are labeled as 1, 2, 3 and 4. R1 is a known router while *1 and *2 are anonymous routers of the type that never return time exceeded error messages. FIG. 2(b) shows the topology that is inferred with pair-wise traceroutes among the four-hosts assuming the paths are symmetric. It will be seen that the two actual anonymous routers become nine anonymous routers in the inferred topology.
Various proposals have therefore been made in the past to reduce this problem by merging anonymous routers in inferred topologies while meeting a number of consistency requirements, including: (a) trace preservation, the inferred topology should agree with all the traceroute paths; and (b) distance preservation, the length of the shortest paths between two nodes in the inferred topology should not be shorter than the traceroute results. Such prior proposals have however been found to be very complex to implement and require very high computational complexity.